/*
 * @Author: gitee_com_zb
 * @Date: 2024-12-11 15:38:19
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-12-11 15:38:30
 * @FilePath: /algorithm/每日一题11.寻找重复数(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/find-the-duplicate-number
 */
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 二分
        // 思路: 检查数组中小于等于mid的个数,若大于mid,则重复数在1到mid区间
        int left = 0, right = nums.size() - 1;
        while(left < right) {
            int mid = left + ((right - left) >> 2);
            int count = 0;
            for(auto &x : nums) {
                if(x <= mid) count++;
            }
            if(count <= mid) left = mid + 1;
            else right = mid;
        }
        return left;
        // 快慢指针(链表环问题)
        // int slow = 0, fast = 0;
        // do {
        //     slow = nums[slow];
        //     fast = nums[nums[fast]];
        // } while(slow != fast);
        // slow = 0;
        // while(slow != fast) {
        //     slow = nums[slow];
        //     fast = nums[fast];
        // }
        // return slow;
    }
};